public class 获取所有钥匙的最短路径 {
    public static int MAXN = 31;
    public static char[][] grid = new char[3][5];
    public static boolean[][][] vis = new boolean[3][5][64];
    public static int[][] queue = new int[3 * 5 * 64][3];
    public static int n,m;
    public static int l,r;
    public static int[] move = {1,0,-1,0,1};
    public static int shortestPathAllKeys1(String[] grids) {
        n = grids.length;
        m = grids[0].length();
        l = r = 0;
        // 找到钥匙, 因为钥匙只有 6 把, 所以使用 int 的前 6 位来进行表示
        int keys = 0;
        // 字符串数组太恶心了, 使用填一下表格, 并找出所有的钥匙, 并添加源点到队列里
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = grids[i].charAt(j);
                if (grid[i][j] == '@') {
                    add(i, j, 0);
                    // 标记这个点已经走过了
                    vis[i][j][0] = true;
                }
                if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {
                    // 位运算添加
                    keys |= (1 << (grid[i][j] - 'A'));
                }
            }
        }
        // 最终的结果
        int ans = 0;

        // 此处采用 bfs 来进行遍历
        while (l < r) {
            int size = r - l;
            ans++;
            while (size-- > 0) {
                int[] t = queue[l++];
                int a = t[0]; // 坐标 i
                int b = t[1]; // 坐标 j
                int c = t[2]; // 钥匙的状态
                for (int i = 0; i < 4; i++) {
                    int x = a + move[i];
                    int y = b + move[i + 1];
                    if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y][c]) {
                        // 找到空房间, 或者重新回到源点, 但是此时是状态不同的
                        if (grid[x][y] == '.' || grid[x][y] == '@') {
                            add(x, y, c);
                            vis[x][y][c] = true;
                        } else if (grid[x][y] >= 'A' && grid[x][y] <= 'F') {
                            // 找到锁, 如果有钥匙的话添加进去, 没有的话就标记一下这个点不需要添加
                            if (((1 << (grid[x][y] - 'A')) & c) != 0) {
                                add(x, y, c);
                            }
                            vis[x][y][c] = true;
                        } else if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {
                            // 找到了钥匙, 判断是否找到全部的钥匙
                            int nc = (1 << (grid[x][y] - 'a')) | c;
                            if (nc == keys) {
                                return ans;
                            }
                            add(x, y, nc);
                            vis[x][y][nc] = true;
                        } else if (grid[x][y] == '#') {
                            // 遇到墙只标记
                            vis[x][y][c] = true;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < r; i++) {
            System.out.println("第" + (i + 1) +"次 "+ "i = " + queue[i][0] + " ,j = " + queue[i][1] + ",c = "+ queue[i][2]);
            System.out.println();
        }
        return -1;
    }
    private static void add(int i, int j, int k) {
        queue[r][0] = i;
        queue[r][1] = j;
        queue[r++][2] = k;
    }

    public static void main(String[] args) {
        String[] grid = {
                "@...a",
                ".###A",
                "b.BCc"
        };
    }

    public static int shortestPathAllKeys(String[] grids) {
        n = grids.length;
        m = grids[0].length();
        l = r = 0;
        // 找到钥匙, 因为钥匙只有 6 把, 所以使用 int 的前 6 位来进行表示
        int keys = 0;
        // 字符串数组太恶心了, 使用填一下表格, 并找出所有的钥匙, 并添加源点到队列里
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = grids[i].charAt(j);
                if (grid[i][j] == '@') {
                    add(i, j, 0);
                    // 标记这个点已经走过了
                    vis[i][j][0] = true;
                }
                if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {
                    // 位运算添加
                    keys |= (1 << (grid[i][j] - 'A'));
                }
            }
        }
        // 最终的结果
        int ans = 0;

        while (l < r) {
            int size = r - l;
            ans++;
            int a,b,c;
            while (size-- > 0) {
                a = queue[l][0]; // 坐标 i
                b = queue[l][1]; // 坐标 j
                c = queue[l++][2]; // 钥匙的状态
                for (int i = 0; i < 4; i++) {
                    int x = a + move[i];
                    int y = b + move[i + 1];
                    int nc = c;
                    if (x < 0 || y < 0 || x == n || y == m || vis[x][y][c] || grid[x][y] == '#') {
                        // 遇到墙或者是越界
                        continue;
                    }
                    if (grid[x][y] >= 'A' && grid[x][y] <= 'F' && ((1 << (grid[x][y] - 'A')) & nc) == 0) {
                        // 找到锁没有对应的钥匙
                        continue;
                    }
                    if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {
                        // 是一把锁
                        nc = (1 << (grid[x][y] - 'a')) | c;
                    }
                    if (nc == keys) {
                        return ans;
                    }
                    if (!vis[x][y][c]) {
                        add(x, y, nc);
                    }
                }
            }
        }
        for (int i = 0; i < r; i++) {
            System.out.println("第" + (i + 1) +"次 "+ "i = " + queue[i][0] + " ,j = " + queue[i][1] + ",c = "+ queue[i][2]);
            System.out.println();
        }
        return -1;
    }
}
